package engine.operators;

import its.util.RandomFactory;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import engine.ObjectiveFunction;
import engine.Operator;
import engine.Population;
import engine.individuals.util.IndividualsComparator;

/**
 * 
 * @author test
 *
 * @param <T>
 */
public class RouletteReproduction<T> implements Operator<T> {

	private static final double MIN_VALUE = 1;
	private ObjectiveFunction<T> objFun;
	private IndividualsComparator<T> comparator;

	public RouletteReproduction(ObjectiveFunction<T> objFun) {
		this.objFun = objFun;
		this.comparator = new IndividualsComparator<T>(objFun);
	}

	@Override
	public Population<T> apply(Population<T> population) {

		Population<T> result = new Population<T>(
				new ArrayList<T>(population.size()));
		
		List<T> individuals = population.getIndividuals();
		Collections.sort(individuals, comparator);
		T minIndividual = individuals.get(0);
		double minValue = objFun.compute(minIndividual);
		double fitnessSum = sum(population.getIndividuals()) - minValue
				* individuals.size();
		List<Double> probMap = new ArrayList<Double>(population.size());
		
		int j = 0;
		for (T ind : individuals) {
			if (j == 0) {
				probMap.add((objFun.compute(ind) - minValue + MIN_VALUE) / fitnessSum);
			} else {
				probMap.add(((objFun.compute(ind) - minValue) / fitnessSum) + probMap.get(j-1));
			}
			++j;
		}
		
		for (int i = 0; i < population.size(); i++) {
			double p = RandomFactory.getNextDouble();
			int drawedIndex = findIndex(probMap, p);
			result.addIndividual(individuals.get(drawedIndex));
		}
		
		return result;
	}

	private int findIndex(List<Double> probList, double p) {
		return findIndex(probList, p, 0, probList.size() - 1);
	}

	private int findIndex(List<Double> probList, double p, int low, int high) {
		
		if (low + 1 < high) {
			int mid = (low + high) / 2;
			double midVal = probList.get(mid);
			
			if (p <= midVal) {
				return findIndex(probList, p, low, mid);
			} else {
				return findIndex(probList, p, mid, high);
			}
		} else {
			return high;
		}
	}

	private double sum(List<T> individuals) {
		double sum = 0.0d;
		
		for (T ind : individuals) {
			sum += objFun.compute(ind);
		}
		sum += MIN_VALUE;
		
		return sum;
	}

}
